package com.aqie.medium.bitOperation;

import java.util.HashSet;
import java.util.Set;

/**
 * 318 两个不含公共字母的单词乘积最大长度
 * 不存在则返回0
 */
public class MaxProduct {
    /**
     * 位运算
     * @param words
     * @return
     */
    public int maxProduct(String[] words){
        /**
         全是小写字母, 可以用一个32为整数表示一个word中出现的字母,
         hash[i]存放第i个单词出现过的字母, a对应32位整数的最后一位,
         b对应整数的倒数第二位, 依次类推. 时间复杂度O(N^2)
         判断两两单词按位与的结果, 如果结果为0且长度积大于最大积则更新
         **/
        int n = words.length;
        int[] hash = new int[n];
        int max = 0;
        for(int i = 0; i < n; ++i) {
            for(char c : words[i].toCharArray())
                hash[i] |= 1 << (c-'a');
        }

        for(int i = 0; i < n-1; ++i) {
            for(int j = i+1; j < n; ++j) {
                if((hash[i] & hash[j]) == 0)
                    max = Math.max(words[i].length() * words[j].length(), max);
            }
        }
        return max;
    }

    /**
     * 暴力解法
     * @param words
     * @return
     */
    public int maxProduct2(String[] words) {
        int max = 0;
        for (int i = 0; i < words.length - 1; i++){
            Set<Character> set = new HashSet<>();
            for (char c : words[i].toCharArray()){
                set.add(c);
            }
            P:for (int j = i + 1; j < words.length; j++){
                if (words[i].length() * words[j].length() <= max){
                    continue ;
                }
                for (char c : words[j].toCharArray()){
                    if (set.contains(c)){
                        continue P;
                    }
                }
                max = words[i].length() * words[j].length();
            }
        }
        return max;
    }

    /**
     * 暴力解法 是上面六倍时间
     * @param words
     * @return
     */
    public int maxProduct3(String[] words){
        if (words == null || words.length == 0) return 0;

        int maxValue = 0;
        for (int i = 0; i < words.length; i++){
            String s1 = words[i];
            for (int j = i + 1; j < words.length; j++){
                String s2 = words[j];
                if (look(s1, s2)){
                    continue;
                }
                int tmp = s1.length() * s2.length();
                if (tmp > maxValue) maxValue = tmp;
            }
        }
        return maxValue;
    }

    private boolean look(String s1, String s2) {
        for (int i = 0; i < s2.length(); i++){
            if (s1.contains(s2.substring(i, i + 1))) return true;
        }
        return false;
    }

    public static void main(String[] args) {
        String[] arr = {"abcw","baz","foo","bar","xtfn","abcdef"};

        String[] arr2 = {"a","ab","abc","d","cd","bcd","abcd"};
    }
}
